package com.zwj.interview.动态规划.背包问题;

import java.util.Arrays;

/**
 * 题目：给定正整数数组coins表示硬币的面额和一个目标总额t，请计算凑出总额t至少需要的硬币数目。
 * 每种硬币可以使用任意多枚。如果不能用输入的硬币凑出给定的总额，则返回-1。
 * 例如，如果硬币的面额为[1，3，9，10]，总额t为15，那么至少需要3枚硬币，即2枚面额为3的硬币及1枚面额为9的硬币
 */
public class 兑换硬币1 {

    /**
     * 分析：
     * 如果将每种面额的硬币看成一种物品，而将目标总额看成背包的容量，那么这个问题等价于求将背包放满时物品的最少件数。
     * 值得注意的是，这里每种面额的硬币可以使用任意多次，因此这个问题不再是0-1背包问题，
     * 而是一个无界背包问题（也叫完全背包问题)
     *
     * 用函数f（i，j）表示用前i种硬币（coins[0，…，i-1]）凑出总额为j需要的硬币的最少数目。
     * 当使用0枚标号为i-1的硬币时，f（i，j）等于f（i-1，j）（用前i-1种硬币凑出总额j需要的最少硬币数目，
     * 再加上1枚标号为i-1的硬币）；当使用1枚标号为i-1的硬币时，f（i，j）等于f（i-1，j-coins[i-1]）加1（用前i-1种硬币凑出总额j-coins[i-1]需要的最少硬币数目，
     * 再加上1枚标号为i-1的硬币）；以此类推，当使用k枚标号为i-1的硬币时，f（i，j）等于f（i-1，j-k×coins[i-1]）加k（用前i-1种硬币凑出总额j-k×coins[i-1]需要的最少硬币数目，
     * 再加上k枚标号为i-1的硬币）。由于目标是求出硬币数目的最小值，因此f（i，j）是上述所有情况的最小值.该状态转移方程可以用如下等式表示：
     * f (i,j)=min(f(i-1,j-k×coins[i-1])+k)(k×coins[i-1]≤j)
     * 如果硬币有n种，目标总额为t，那么f（n，t）就是问题的解
     *
     * 当j等于0（即总额等于0）时，f（i，0）都等于0，即从前i种硬币中选出0个硬币，使总额等于0。
     * 当i等于0且j大于0时，即用0种硬币凑出大于0的总额，这显然是不可能的，但可以用一个特殊值表示
     */


    /**
     * 思路二：
     * 用函数f（i）表示凑出总额为i的硬币需要的最少数目。需要注意的是，
     * 这个函数只有一个参数，表示硬币的总额。如果目标总额为t，那么f（t）就是整个问题的解。
     * <p>
     * 为了凑出总额为i的硬币，有如下选择：在总额为i-coins[0]的硬币中添加1枚标号为0的硬币，
     * 此时f（i）等于f（i-coins[0]）+1（在凑出总额为i-coins[0]的最少硬币数的基础上加1枚标号为0的硬币）；
     * 在总额为i-coins[1]的硬币中添加1枚标号为1的硬币，此时f（i）等于f（i-coins[1]）+1。
     * 以此类推，在总额为i-coins[n-1]的硬币中添加1枚标号为n-1的硬币，此时f（i）等于f（i-coins[n-1]）+1。
     * 因为目标是计算凑出总额为i的硬币，所以f（i）是上述所有情况的最小值。该状态转移方程可以表示为：
     * f(i)=min(f(i-coins[j])+1)(coins[j]≤i)
     * 显然，f（0）等于0，即凑出总额0至少需要0枚硬币
     *
     * dp[i]=x表示凑出金额为i至少需要x枚硬币
     */
    public int coinChange(int[] coins, int target) {
        int max = target + 1;
        //dp[x]=y表示 要凑出金额为x,需要y枚硬币
        int[] dp = new int[target + 1];
        //初始化数组
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[target] > target ? -1 : dp[target];
    }

}
